1. Technical Field
Aspects of the present invention generally relate to proof-of-knowledge (POK), which allows a prover to convince a verifier of its knowledge of the multiple secret DH-exponents, corresponding to some public (fixed and/or ephemeral) DH-components, while revealing no knowledge of the supposed secrets. The POK is aimed for concurrent non-malleability security, robust secrecy exposure resistance, privacy preserving and on-line efficiency. By viewing fixed DH-components as public-keys and each party proving its knowledge of secret DH-exponents using the invented POK method, in exemplary embodiments, this particularly yields authenticated Diffie-Hellman key-exchange (DHKE) protocols.
2. Description of the Related Art
The Diffie-Hellman key-exchange (DHKE) protocol 101, illustrated in FIG. 1, is at the root of public-key cryptography (PKC), and is one of the main pillars of both theory and practice of cryptography. Generally, key exchange plays a central role in modern cryptography, in the sense that it serves as the bridge between public-key cryptography and secret-key cryptography (SKC). Specifically, PKC is convenient for use but inefficient, while SKC is efficient but inconvenient for use. In common applied crypto applications, PKC is mainly used to generate and share a secret-key among users, and then SKC comes into force with the shared secret-key. Particularly important to applied crypto engineering, DHKE underlies a wide range of key industrial standards for ensuring network security. Another reason that DHKE is important and popular is that it supports implementations based on elliptic curve cryptography.
Despite its seeming conceptual simplicity, designing correct and secure DHKE protocols turns out to be extremely error prone and can be notoriously subtle (the literature is filled with DHKE protocols that have been found to contain certain security flaws). The reason for this is the high system complexity and enormous number of subtleties surrounding the definition and design/analysis of sound DHKE protocols. Telling apart secure from insecure protocols can hardly be done by immediate inspection or using simple intuition. Therefore, it is of utmost importance to come up with reasonable frameworks/models to understand the underlying rational for sound design choices, to formulate the bare-bone nature of sound DHKE, to allow and guide successful novel implementations, and to provide new insights into both the design and analysis of DHKE (as well as to debdug the shortcomings of existing protocols). In general, coming up with reasonable frameworks/models of complex systems is arguably one of the most important as well as hardest parts of research.
A list of models and frameworks for the provable security of DHKE are developed in the literature. Unfortunately, due to the high system complexity and subtle nature of DHKE, all known exiting frameworks and models turn out to be insufficient for capturing some essential security properties of DHKE. Also, some models and frameworks are themselves too complicated to be worked with easily, which may cause complicated and potentially error-prone lengthy proofs (as well as potential misunderstanding or misinterpretation of the actual security guarantee).
Recently, the inventors introduced a new framework for DHKE protocols, which is referred to as the Yao-Yao-Zhao (YYZ) framework. For presentation simplicity, the YYZ framework is briefly recalled here in the two-party setting between two parties Â and {circumflex over (B)}, and it is assumed that the party Â plays the role of the initiator and the party {circumflex over (B)} plays the role of the responder. Let G′ be a finite Abelian group of order N, G be a subgroup of order q of G′, and g is a generator of G, where q is a large prime (typically, |q|=160) and the computational Diffie-Hellman (CDH) assumption holds with respect to G. The inventors use multiplicative notation for the group operation in G′, denote by 1G the identity element of G′ and by
  t  =      N    q  the cofactor. The protocol run between Â and {circumflex over (B)} is denoted as the protocol <Â, {circumflex over (B)}>. Denote by X=gx and x the ephemeral DH-component and ephemeral DH-exponent of the party Â, and by Y=gy and y the DH-component and DH-exponent of the party {circumflex over (B)}, where x and y are taken randomly and independently from Zq*.
To distinguish concurrent sessions locally running at each player's side, an uncorrupted player identifies each local session at its side by its identity and its DH-component sent in this session, e.g., (Â,X). Each local session is also labeled by a tag, which is the concatenation, in the order of session initiator and then session responder, of (available) players' identities and (whether static public-key and ephemeral) DH-component contributions, e.g., Tag=(Â,{circumflex over (B)},X,Y) for a completed (i.e., successfully finished) session of the original DH-protocol. (For the general multi-party case, the tag of each session is set to be the concatenation, in some agreed order, of all players' identities and their DH-component contributions.) For an incomplete or aborted session, its tag is determined by the available partial transcript. Note that one of the players Â or {circumflex over (B)}, but not all, in the tag may actually be impersonated or just controlled by an adversary.
For a completed local session (Â,X) (resp., ({circumflex over (B)},Y)), referred to as the test-session, at the side of the uncorrupted player Â (resp., {circumflex over (B)}) with the tag Tag=(Â,{circumflex over (B)},X,Y), we define its matching session to be the local session (Ĉ,Y) (resp., (Ĉ,X)) run at the side of any uncorrupted player Ĉ, in case that such matching session exists. Once a session is finished, the honest players always erase the ephemeral private states generated during the session, and only keep in privacy the session key output; Sessions can also be expired, and for expired sessions the session keys are also erased.
Polynomially many concurrent executing instances (sessions) of the protocol <Â,{circumflex over (B)}> take place in an asynchronous setting (such as the Internet), and all communication channels are assumed to be unauthenticated and controlled by a probabilistic polynomial-time (PPT) concurrent man-in-the-middle (CMIM) adversary  In addition,  takes some arbitrary auxiliary input z∈{0,1}*, which captures arbitrary information collected/eavesdropped by  over the network from the executions of arbitrary (possibly different) protocols prior to its interactions with the instances of Â or {circumflex over (B)}. The CMIM  can do whatever it wishes. Besides scheduling exchanging messages at its wish,  is also allowed to access secret information against any honest player instance, via attacks of four types: (1) Ephemeral private state reveal on an incomplete sessions, by which  learns the ephemeral private states generated by the honest player during the incomplete session; (2) Session-key reveals on a completed and unexpired session; (3) Static secret-key reveals on an honest player; (4) Player corruptions, by which  totally controls the corrupted player. A local session run at the side of an honest player is called internally-unexposed, if this player does not suffer from the above exposure attacks (1) and (4) until the session is completed.
Within the mentioned YYZ framework for DHKE protocols, the inventors formulated a new notion of security for DHKE protocols: tag-based robust non-malleability (TBRNM). The philosophy of TBRNM, formulated by the YYZ framework, is to achieve the most robust security guarantee while relying on the minimal secrecy. TBRNM essentially says that an uncorrupted player, who successfully finishes an internally-unexposed session of distinct tag (which is referred to as the test session), should have the guarantee: its peer (whether honest or malicious) must “know” both the according DH-exponent and the secret-key (corresponding to the DH-component and the public-key sent and alleged by its peer in this session). This guarantee holds even if the adversary learns the static secret-key of any uncorrupted player, ephemeral private state information of any other sessions (other than the test-session and possibly its matching session), and the session-key outputs of any completed and unexpired sessions.
For the trade-off between security and privacy, two levels of TBRNM security are formulated within the YYZ framework; (1) Tag-binding TBRNM, which holds as long as only the test-session is internally-unexposed. Tag-binding TBRNM is mainly for protocols where each player knows (and makes sure the validity of) its peer's identity and public-key prior to the protocol run; (2) Privacy-preserving TBRNM, which holds as long as both the test-session and its matching session are internally-unexposed. Privacy-preserving TBRNM is mainly for protocols that may work in the post-ID model (i.e., a party learns its peer's identity or public-key information only during the evolution of the protocol run, and even at the last round of the session).
It is clarified by the inventors that the TBRNM security, together with independent session-keys for sessions of different tags, implies most essential security properties expected for DHKE protocols. Also, the goal of tag-based robust non-malleability would naturally be a fundamental principle for any sound and robust DHKE protocols.
In this application, the inventors re-investigate and analyze DHKE protocols in the mentioned YYZ framework for DHKE. The inventors observe and clarify some fundamental issues that were not previously (at least explicitly) addressed in the literature. These issues are about the subtleties of using the shared DH-secret as a building block (particularly multiplied by other DH-secrets) for building more advanced and complex cryptographic objects.
Among all DHKE protocols based on public-key authentications, the MQV protocol shown in FIG. 2, 201 and 203 (developed by Menezes et al in Second Workshop on Selected Areas in Cryptography SAC '95, pages 22-32, November 1995) and the HMQV protocol shown in FIGS. 2, 201 and 203 (developed by Krawczyk in Advances in Cryptology-Proceedings of CRYPTO 2005, pages 546-566, August 2005) are among the most successful and possibly the most efficient authenticated Diffie-Hellman protocols based on public-key authentication. For presentation simplicity, the MQV and HMQV protocols are referred to as the (H)MQV protocol family. Let Â (resp., {circumflex over (B)}) be of public-key A=ga (resp., B=gb) and secret-key a (resp., b), and HK be a hash function of k-bit output (where k is the security parameter), the (H)MQV protocol family is recalled in FIG. 2 (201, 202, 203). (H)MQV has been widely standardized. In particular, it has been announced by the US National Security Agency (NSA) as the key exchange mechanism underlying “the next generation cryptography to protect US government information”, which includes the protection of “classified or mission critical national security information”.
Despite an arguable evolution history of (H)MQV, it is commonly believed that the updated version of (H)MQV, with security analysis and discussions in the Canetti Krawczyk framework, should be robust enough and should have no other security weaknesses. Particularly in view of the nearly optimal efficiency of (H)MQV, it may be suggested that (H)MQV achieves the best for DHKE in the integrity of security and protocol efficiency.
The inventors re-investigate (H)MQV in accordance with the mentioned YYZ framework for DHKE, and show that (H)MQV fails in achieving tag-based robust non-malleability in general. This is demonstrated by concrete attacks. That is, by malleating messages from other honest parties, an adversary can successfully finish a session of (H)MQV with an honest player, but actually without knowing either the secret-key or the ephemeral DH-exponent alleged and sent by the adversary. This is due to the weakness and vulnerability of the underlying building tool used in (H)MQV for demonstrating the knowledge of secret-key and ephemeral DH-exponent of each player. The inventors then propose some fixing approaches to the weakness identified by the inventors in the YYZ framework.
Besides the security weakness of the (H)MQV protocol, the inventors further note some disadvantages of the (H)MQV protocols: (1) (H)MQV does not allow pre-computation of parts of the shared session-key to improve on-line efficiency; (2) (H)MQV does not support post-ID computability of the shared session-key; (3). (H)MQV does not support parallel computation of parts of shared session-key and explicit subgroup test of peer's ephemeral DH-components; (4) (H)MQV does not guarantee deniability (a very useful property for preserving players' privacy).
The above identified weaknesses and disadvantages of (H)MQV may reflect, despite its appearing success, the underlying design rational and building tools of (H)MQV may not be so sound and robust as commonly expected. This raised concerns to the present inventors to design authenticated DHKE protocols, towards to the optimal tradeoff among security, privacy and protocol efficiency, under fundamentally new design rational and with fundamentally new building tools.